Educational Codeforces Round 108 (Div. 2) D Maximum Sum of Products
$ dp_{l, r} := 区間$ [l, r)を反転した際のスコア として区間DPをしていく. このDPの遷移は次のようになる.
$ r - l \leq 2のとき
あらかじめ累積和を計算しておくことによって高速に求められる.
$ r - l \geq 3のとき
$ dp_{l, r} = dp_{l + 1, r - 1} + a_lb_{r - 1} + a_{r - 1}b_l - a_lb_l - a_{r - 1}b_{r - 1}と更新できる.
定数時間で更新できるので, 計算量は$ O(N^2)となる. なお, 実装の際はメモ化再帰を用いるのが楽である.